#ifndef QUICKSORT_H
#define QUICKSORT_H

#include <bits/stdc++.h>
using namespace std;

template <typename Compareble>
void RandomQuickSort(std::vector<Compareble>& arr,int left,int right){
    if (left > right){return;}
    Compareble temp=0;
    if(right-left<=10){
        for(int i=left;i<right;i++){
            for(int j=i+1;j<=right;j++){
                if(arr[i]>arr[j]){
                    temp = arr[j];
		            arr[j] = arr[i];
		            arr[i] = temp;
                }
            }
        }
        return;
    }

    int i = left;
    int j = right;
    srand(time(0));
    int k=rand()%(right-left+1)+left;
    temp=arr[k];
    arr[k]=arr[right];
    arr[right]=temp;
    Compareble flag = arr[right];
    while (i < j)
    {
        while (arr[i] <= flag && i < j)
        {
            i++;
        }
        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
        while (arr[j] >= flag && i < j)
        {
            j--;
        }
        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    arr[i]=flag;
	//将中值左,右侧的数据分别递归进行排序
	RandomQuickSort<Compareble>(arr, left, i - 1);
	RandomQuickSort<Compareble>(arr, i + 1, right);
}

template <typename Compareble>
void Median3QuickSort(std::vector<Compareble>& arr,int left,int right){
    if (left > right){return;}
    Compareble temp=0;
    if(right-left<=10){
        for(int i=left;i<right;i++){
            for(int j=i+1;j<=right;j++){
                if(arr[i]>arr[j]){
                    temp = arr[j];
		            arr[j] = arr[i];
		            arr[i] = temp;
                }
            }
        }
        return;
    }

    int Middle = (left + right) / 2;  
    if (arr[left] > arr[Middle])
    {
        temp=arr[left];
        arr[left]=arr[Middle];
        arr[Middle]=temp;
    }
    if (arr[left] > arr[right])
    {
        temp=arr[left];
        arr[left]=arr[right];
        arr[right]=temp;
    }
    if (arr[Middle] > arr[right])  
    {
        temp=arr[Middle];
        arr[Middle]=arr[right];
        arr[right]=temp;
    }
    temp=arr[Middle];
    arr[Middle]=arr[right];
    arr[right]=temp;

    int i = left;
    int j = right;
    Compareble flag = arr[right];
    while (i < j)
    {
        while (arr[i] <= flag && i < j)
        {
            i++;
        }
        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
        while (arr[j] >= flag && i < j)
        {
            j--;
        }
        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    arr[i]=flag;
 
	//将中值左,右侧的数据分别递归进行排序
	Median3QuickSort(arr, left, i - 1);
	Median3QuickSort(arr, i + 1, right);
}  

#endif